package com.yww.leetcode.binarytree;

import com.yww.leetcode.common.TreeNode;

import java.util.Arrays;

/**
 * @author yww
 * @description 105. 从前序与中序遍历序列构造二叉树
 * @since 2024/2/13 19:02
 */
public class BuildTree105 {
    // 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
    // inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal, null, null);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                int[] inorderLeft = Arrays.copyOfRange(inorder, 0, i); // 划分左子树
                int[] inorderRight = Arrays.copyOfRange(inorder, i + 1, inorder.length); // 划分右子树

                int[] preorderLeft = Arrays.copyOfRange(preorder, 1, i + 1); // 划分左子树
                int[] preorderRight = Arrays.copyOfRange(preorder, i + 1, preorder.length); // 划分右子树
                root.left = buildTree(preorderLeft, inorderLeft);
                root.right = buildTree(preorderRight, inorderRight);
                break;
            }
        }
        return root;
    }
}
